package org.shj.suanfa

/**
 * 求两个数的最大公因数。公因数是指能同时被两个数整除的数。如： 50 和 15 的最大公因数是 5
 */
object MaxGongYinZi {
  def main(args: Array[String]): Unit = {
    val m = 1989
    val n = 1590
    
    // 能比较容易想到的一种方法
    method1(m, n)
    
    /**
     * 欧几里德算法
     * 有一个定理： 若 M > N， 则 M mod N < M/2
     */
    method2(m, n)
  }
  
  def method1(m: Int, n: Int){
    var k = Math.sqrt(n).toInt + 1
    var i = 1
    while(i < k){
      if(m % k == 0 && n % k == 0){
        println(k)
        return
      }
      k -= 1
    }
  }
  
  def method2(m: Int, n: Int){
    var big = m
    var little = n
    while(little != 0){
      var rem = big % little
      big = little
      little = rem
    }
    println(big)
  }
}